package com.lwx.chapter7;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 稠密图 - 邻接矩阵
 */
public class DenseGraph {
    //顶点数
    private int n;
    //边数
    private int m;
    /**
     * 是否为有向图
     */
    private boolean directed;
    /**
     * 任意两个顶点之间是否有边
     */
    List<List<Boolean>> g;

    public DenseGraph(int n, Boolean directed) {
        this.n = n;
        this.m = 0;
        this.directed = directed;
        g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List levelList = new ArrayList();
            for (int j = 0; j < n; j++) {
                levelList.add(false);
            }
            g.add(levelList);
        }
    }

    int V() {
        return n;
    }

    int E() {
        return m;
    }

    /**
     * 在顶点v和顶点e之间建立一条边
     *
     * @param v
     * @param w
     */
    void addEdge(int v, int w) {
        //避免边数重复计数
        if(hasEdge(v,w)){
            return;
        }
        if (v < n && v >= 0 && w>=0 && w < n) {
            List<Boolean> gLevelList = g.get(v);
            gLevelList.add(w, true);
            if (!directed) {
                List<Boolean> wLevelList = g.get(w);
                wLevelList.add(v , true);
            }
            m++;
        }
    }

    Boolean hasEdge(int v, int w){
        if (v < n && v >= 0 && w>=0 && w < n) {
            List<Boolean> gLevelList = g.get(v);
            return gLevelList.get(w);
        }
        return false;
    }

    //使用迭代器来实现，返回指定节点的相连节点
    class  adjIterator{
        DenseGraph graph;
        int v;
        //返回的下标值
        int index;
        public adjIterator( DenseGraph graph, int v){
            this.v = v;
            this.index = -1;
            this.graph = graph;

        }

        /**
         * v节点对应的第一个元素
         * @return
         */
        int begin(){
            index = -1;
            return next();
        }

        /**
         *
         * @return
         */
        int next(){
            index ++;
            if(index < this.graph.g.size()){
                List<Boolean> vLevelList = graph.g.get(v);
                for ( index = index; index < vLevelList.size(); index++) {
                    if(vLevelList.get(index)){
                        return index;
                    }
                }
            }
            return -1;
        }

        /**
         * v节点的是否遍历结束
         * @return
         */
        boolean end(){
            return index >= this.graph.V();
        }
    }
}
